package 剑指offer;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author: tyy 剑指 Offer
 * 496. 下一个更大元素 I
 * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
 * 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
 * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
 * <p>
 * 示例 1:
 * 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
 * 输出: [-1,3,-1]
 * 解释:
 * 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
 * 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
 * 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
 * @create: 2021-10-21 17:40
 * @description:
 **/
public class Solution10 {
    /**
     * 亲们记住，一但要求下一个更大的元素，就是用单调栈解，力扣题库相似的题目都是这个解法。
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }


    /**
     * 通过Stack、HashMap解决
     先遍历大数组nums2，首先将第一个元素入栈；
     继续遍历，当当前元素小于栈顶元素时，继续将它入栈；当当前元素大于栈顶元素时，栈顶元素出栈，此时应将该出栈的元素与当前元素形成key-value键值对，存入HashMap中；
     当遍历完nums2后，得到nums2中元素所对应的下一个更大元素的hash表；
     遍历nums1的元素在hashMap中去查找‘下一个更大元素’，当找不到时则为-1。
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement3(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<Integer>();
        HashMap<Integer, Integer> hasMap = new HashMap<Integer, Integer>();

        int[] result = new int[nums1.length];

        for(int num : nums2) {
            while(!stack.isEmpty() && stack.peek()<num){
                hasMap.put(stack.pop(), num);
            }
            stack.push(num);
        }

        for(int i = 0; i < nums1.length; i++) result[i] = hasMap.getOrDefault(nums1[i], -1);

        return result;
    }
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        int[] numcopy = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int num1 = nums1[i];
            int index = -1;
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == num1) {
                    if (j == nums2.length - 1) {
                        numcopy[i] = -1;
                        break;
                    }
                    index = j;
                }
                if (index != -1 && j > index) {
                    if (nums2[j] > num1) {
                        numcopy[i] = nums2[j];
                        break;
                    } else if (j == nums2.length - 1) {
                        numcopy[i] = -1;
                        break;
                    }
                }
            }
        }
        return numcopy;
    }

    public static void main(String[] args) {
        int nums1[] = {2, 4};
        int nums2[] = {1, 2, 3, 4};

        int[] ints = new Solution10().nextGreaterElement(nums1, nums2);
        System.out.println("ints = " + Arrays.toString(ints));
    }
}

/**
 * JAVA版——提供完整思路
 * <p>
 * --------------------------------------------
 * <p>
 * 【变量说明】
 * <p>
 * 数组长度为 n ，最小操作次数为 k ，操作前数组的最小值为 min ，操作前数组的最大值为 max ，操作前数组的第二大值为 max2 ，操作前数组所有数和为 sum 。
 * <p>
 * --------------------------------------------
 * <p>
 * 【思路分析】
 * <p>
 * 假设你可以无误执行完整个流程，这样可以搭建流程执行前后的桥梁。
 * <p>
 * 将操作流程前后的量进行分析，找到一个不变量，构成等式，进行求解。
 * <p>
 * 根据题意，每次操作将会使 n - 1 个元素增加 1 。由于你执行了 k 次，所以一共会使 sum 增加 k * (n - 1) 。即操作结束后数组的和为 sum + k * (n - 1) 。
 * <p>
 * 贪心部分：在整个流程的每次操作中，最小的那个值都会增加 1 。（贪心的证明在下个板块，建议最后看）
 * <p>
 * 由贪心可知，经过k 步后， min 变为了 min + k ，也意味着此时数组的每一项都变为了 min + k ，所以操作结束后数组的和为 n * (min + k) 。
 * <p>
 * 根据等量代换：
 * <p>
 * sum + k * (n - 1) = n * (min + k)
 * sum + k * n - k = n * min + n * k
 * sum - k = n * min
 * k = sum - n * min
 * 所以，最短操作次数为 k = sum - n * min 。
 * <p>
 * 先求和再减去长度n个最小值，不是相当于每一项减去最小值再求和吗？
 * <p>
 * 数学证明：（证明公式为latex代码，课根据需要转为公式查看）
 * <p>
 * \sum_{i=0}^{i=n-1}{nums\left[ i \right]}-n\times \min =\sum_{i=0}^{i=n-1}{nums\left[ i \right]}-\sum_{i=0}^{i=n-1}{\min}=\sum_{i=0}^{i=n-1}{nums\left[ i \right] -\min}
 * 最终结论：k = SUM(nums[i] - min)
 * <p>
 * --------------------------------------------
 * <p>
 * 【贪心证明】
 * <p>
 * 结论：在整个流程的每次操作中，最小的那个值都会增加 1 。
 * <p>
 * 证明过程：
 * <p>
 * 这个贪心可能不好理解，这里我们可以分成两个部分来理解：
 * <p>
 * 第一部分就是 max2 在追赶 max 的过程，设这个过程执行了 k' 次，在这 k' 次中，每次必然会使 max 的以外的元素增加 1 ，直到产生一个新的元素大于 max 为止（这个元素就是 max2 位置的元素，记为 max'），这个阶段 min 每次都增加了 1 ，并且这一步的前一步，max' 是等于max 的，之后的每一步都是 max' 和 max 争夺最大值的阶段， max' 和 max 轮流增加 1 ，其他元素每次的增加 1。由于其他元素的增速是大于 max' 和 max 的，所以很快会有个数大于 max' 和 max （也就是原数组的第三大的数，记为 max''），之后就是 max 和 max' 和 max'' 轮流作为最大值的过程。……
 * <p>
 * 第二部分就是第一个部分的临界阶段，也就是由于增速差除了原来最小的数 min 其他数轮流作为最大值时，这个时候 min 所在位置的数会以一种很快的速度增长直到他比最大值的数小 1为止（也就是支出现两种数为止），然后除了最大值的数，其他都增加 1 ，直到弥补和最小值之间的差为止。这个部分 min 也一直在增加。
 * <p>
 * 例题：这里以[1,2,3,4] 为例
 * <p>
 * 第一个部分：
 * <p>
 * [2,3,4,4]：其余数都在追赶你索引为3的数，最小数从1增加为了2。
 * <p>
 * [3,4,5,4]：索引为2的数超过了索引为3的数，最小数从2增加为了3。
 * <p>
 * [4,5,5,5]：其余数都在追赶你索引为2的数，最小数从3增加为了4。（此时只有两种类型的数 4 和 5 ，且差值为 1 ，进入第二部分）
 * <p>
 * 第二部分
 * <p>
 * [5,6,5,6]：索引为1的数超过了索引为2的数，最小数从4增加为了5。
 * <p>
 * [6,6,6,7]：其余数都在追赶你索引为1的数，索引为3的数超过了索引为1的数，最小数从5增加为了6。
 * <p>
 * [7,7,7,7]：其余数都在追赶你索引为3的数，最小数从6增加为了7。
 * <p>
 * --------------------------------------------
 */
